#pragma once
#include "gtest\gtest.h"
#include "binSearch.h"
#include "ISort.h"
#include <iostream>
#include <stack>
using namespace std;
void revert( char* a, int n )
{
	if( n <= 0 )
	{
		return;
	}
	else
	{
		revert( a+1, n-1);
		printf("%c", *a); //printf after recursive call make a reversed order	
	}
}

void revert2( char* a, int n )
{
	for(int i = n; i > 0; i--)
	{
		printf("%c", *(a+i-1));
	}
}
void swap( char* a , char* b)
{
	//a = a ^ b;
	//b = a ^ b;
	//a = a ^ a;
	char t = *a; 
	*a = *b; 
	*b = t;
}
//Permutation, the key here the recursive function should always take the orignal string as input
//So use two index s and e
void permute( char* a, int s, int e)
{
	if(a == 0 || *a == '\0')
	{
		//error
		return;
	}

	if( s == e )
	{
		cout << a << endl; 
		//return;
	}

	for( int i = s; i < e; i++)
	{
		swap(a+s, a+i);
		permute(a, s+1, e);
		swap(a+s, a+i);
		//cout << a << endl;
	}
}
//Put all 0 ahead of other elements (with the same order)
void Arrange(int* a, int n)
{
    int k = n - 1 ;
    for (int i = n - 1; i >= 0; --i)
    {
        if (a[i] != 0)
        {
            if (a[k] == 0)
            {
                a[k] = a[i] ;
                a[i] = 0 ;
            }
            --k ;
        }
    }
}
TEST(Search, binSearch)
{
	int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};

	int index1 = binSearch( arr, 0, 10, 8 );

	ASSERT_EQ( 7, index1);

	int index2 = binSearch2( arr, 0, 10, 7 );

	ASSERT_EQ( 6, index2 );
}

int Fib(int n)
{
	if(n <= 1)
		return 1;
	return Fib(n-1) + Fib(n-2);
}

int Fib2(int n)
{
	if( n <= 1)
		return 1;
	int pre1 = 1, pre2=1, fib=0;
	int i = 1;
	while( i < n )
	{
		fib = pre1 + pre2;
		pre2 = pre1;
		pre1 = fib;
		i++;
	}
	return fib;
}

int LCS(int* a, int n)
{
	if( a == 0 ) return 0;
	int* cum = new int[n];
	memset(cum, 0, n);
	cum[0] = a[0];
	for( int i = 1; i < n; ++i)
	{
		cum[i] += cum[i-1];
	}
	int start = 0;
	int len = 1;
	int max = 1;

	for( int i = 1; i < n; ++i)
	{
		if( cum[i] >= cum[start])
		{
			len++;
			if( len > max )
			{
				max = len;
			}
		}
		else
		{
			start = i;
			len = 1;
		}
	}
	return max;
}

TEST(LCS, lcs)
{
	int a[] = {1, -9, -8, -7, 8, 4, 2};
	cout << "LCS = " << LCS(a, 9) << endl;

}
TEST(Fib, fib)
{
	EXPECT_EQ( Fib(5), Fib2(5));
	EXPECT_EQ( Fib(11), Fib2(11));
	EXPECT_EQ( Fib(2), Fib2(2));
	EXPECT_EQ( Fib(0), Fib2(0));
	EXPECT_EQ( Fib(3), Fib2(3));
}

TEST(Sort, qsort)
{
	int arr[] = {20, 46, 88, 33, 1, 55, 44, 2, 11, 99};

	qsort(arr, 0, 9 );

	for( int i = 0; i < 10; i++)
	{
		cout << arr[i] << ",";
	}
	cout << endl;
}

//Find the a subarray whose sum is maximum
int max( int a , int b)
{
	return a > b ? a : b;
}
int MaxSubArray(int* arr,  int len)
{
	if( arr == 0 ) return 0;
	int maxsofar = arr[0];
	int maxsum = arr[0];

	for( int i = 1; i < len; ++i)
	{
		maxsofar = max(arr[i] + maxsofar, arr[i]);
		maxsum = max(maxsofar, maxsum);
	}
	
	return maxsum;
}
int MaxSubArray2(int* arr,  int len)
{
	if( arr == 0 ) return 0;
	int sumSofar	= arr[0];
	int minSumSofar = 0;
	int maxsum      = arr[0];

	for( int i = 1; i < len; ++i)
	{
		sumSofar += arr[i];
		
		if( sumSofar < minSumSofar)  minSumSofar = sumSofar;

		if( sumSofar - minSumSofar > maxsum )
			maxsum = sumSofar - minSumSofar;
	}
	
	return maxsum;
}

TEST(maxSubArray, maxsubarray)
{
	int a[] = {1, -3, 6, 8, -5, -7, 10};

	cout << "Max is = " << MaxSubArray( a, 7) << endl;
}

bool isMatch(char *str, const char* pattern) 
{
  while (*pattern)
    if (*str++ != *pattern++)
      return false;
  return true;
}
 
void replace(char str[], const char *pattern) 
{
	if (str == NULL || pattern == NULL) return;
	char *pSlow = str, *pFast = str;
	int pLen = (int)strlen(pattern);
	while (*pFast != '\0') {
		bool matched = false;
		while (isMatch(pFast, pattern)) {
			matched = true;
			pFast += pLen; //so that pfast skip the len of pattern, pslow is still at the begin of pattern
		}
		if (matched){
			*pSlow++ = 'X';
		}else
		{
		// tricky case to handle here:
		// pFast might be pointing to '\0',
		// and you don't want to increment past it
		if (*pFast != '\0'){
		  *pSlow++ = *pFast++;  // *p++ = (*p)++ , when no match, just do copy
		}
		}
	}
	// don't forget to add a null character at the end!
	*pSlow = '\0';
	
}

TEST(ReplacePattern, replace)
{
	char input[] ="abcdeffdfegabcabc"; 
	replace(input, "abc");
	cout << "Replaced = " << input << endl;


}

string numToAZ(int n)
{
	if( n < 1 )
		return "error";
	
	string out(1, 'a'+n%26);
	n /=26;
	while( n != 0 )
	{
		out = char('a' + (n-1)%26) + out;
		n = (n -1) /26; 
	}
	return out;
}
TEST(AZ, numToAZ)
{
	cout << numToAZ(703) << endl;
}

char* str_str(char* src, char* dest)
{
	if( src == 0 || dest == 0 ) return 0;
	if( *src == '\0' || *dest == '\0') return src;
	char* dst_ptr = dest;
	while( *src != '\0' )
	{
		//Find the first matched char
		//if( *src != *dest ) 
		//{  
		//	src++;
		//}
		//else
		//{
			//Record the start point
			char* src_ptr = src;
			while( *dst_ptr && *src_ptr && *src_ptr == *dst_ptr)
			{
					src_ptr++;
					dst_ptr++;
			}
			if( *dst_ptr == '\0') return src;
			dst_ptr = dest;
			src++;
		//}
	}
	return 0;
}

TEST(str_str, str_str)
{
	//char* p = str_str("bbccddd", "cc"); 
	//cout << "Does string match = " << str_str("bbccddd", "cc") << endl;
	cout << "Does string match = " << str_str("cbccddd", "cc") << endl;

}

TEST(bin_count, bincount)
{
	static int a[] = {1,2,3,4,4,4,4,4,5,6,8,8,9};

	cout << "the count of 4 value = " << bin_count(a, 13, 4) << endl;
	cout << "the count of 8 value = " << bin_count(a, 13, 8) << endl;
	cout << "the count of 1 value = " << bin_count(a, 13, 1) << endl;
	cout << "the count of 9 value = " << bin_count(a, 13, 9) << endl;
	cout << "the count of 10 value = " << bin_count(a, 13, 10) << endl;

}